package com.note.feng.leetcode.algorithms.easy;

import java.util.HashMap;
import java.util.Map;

public class Seventy {

    /**
     * 70 爬楼梯
     * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
     *
     * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
     *
     * 示例 1：
     *
     * 输入：n = 2
     * 输出：2
     * 解释：有两种方法可以爬到楼顶。
     * 1. 1 阶 + 1 阶
     * 2. 2 阶
     * 示例 2：
     *
     * 输入：n = 3
     * 输出：3
     * 解释：有三种方法可以爬到楼顶。
     * 1. 1 阶 + 1 阶 + 1 阶
     * 2. 1 阶 + 2 阶
     * 3. 2 阶 + 1 阶
     *  
     *
     * 提示：
     *
     * 1 <= n <= 45
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/climbing-stairs
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */

    /**
     * 解法：
     * 动态规划：递归实现
     * 每一步都分为走一台阶或者两台阶
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        if(n == 1){
            return 1;
        }
        if(n == 2){
            return 2;
        }
        return climbStairs(n - 1) + climbStairs(n - 2);
    }

    /**
     * 解法：动态规划，方法一的非递归实现
     * @param n
     * @return
     */
    public int climbStairs2(int n) {
        if(n == 1){
            return 1;
        }
        if(n == 2){
            return 2;
        }
        Map<Integer, Integer> map = new HashMap<>();
        map.put(1,1);
        map.put(2,2);
        int step = 3;
        int res = 3;
        while(step <= n){
            res = map.get(step - 1) + map.get(step - 2);
            if(!map.containsKey(step)){
                map.put(step, res);
            }
            step ++;
        }
        return res;
    }

    /**
     * 解法：
     * 动态窗口：知道了1个台阶和2个台阶，需要的步数，就可以计算出3个台阶需要的步数，
     * 随着台阶数量的增加，值需要记录台阶数-1和台阶数-2对应需要的步数即可。
     * @param n
     * @return
     */
    public int climbStairs3(int n) {
        int one = 0;//n-1个台阶需要的步数
        int two = 0;//n-2个台阶需要的步数
        int step = 1;//台阶的起始值；
        int res = 1;//台阶最少有1个，需要一步
        while(step <= n){
            one = two;
            two = res;
            res = one + two;
            step ++;
        }
        return res;
    }
}
